package com.desin.modle.datastruct.algo.divideAlgorithm.countSort;

public class CountSortWorld {
    private int num;

    public void countSort(int[] works,int start,int end){
        if(start>=end){
            return;
        }
        int mid = (end + start)/2;
        countSort(works,start,mid);
        countSort(works,mid+1,end);
        merge(works,start,mid,end);
    }

    private void merge(int[] works, int start, int mid, int end) {
        int[] newArrays = new int[end - start+1];
        int newArraysIndex = 0;
        int leftStart = start,rightStart=mid+1;
        while (leftStart<=start&&rightStart<=end){
            if(works[leftStart]>works[rightStart]){
                num = num + mid - leftStart + 1;
                newArrays[newArraysIndex] = works[rightStart];
                rightStart++;
                newArraysIndex++;
            }else {
                newArrays[newArraysIndex] = works[leftStart];
                leftStart++;
                newArraysIndex++;
            }
        }

        while (leftStart<=mid){
            newArrays[newArraysIndex] = works[leftStart];
            leftStart++;
            newArraysIndex++;
        }

        while (rightStart<=end){
            newArrays[newArraysIndex] = works[rightStart];
            rightStart++;
            newArraysIndex++;
        }

        for(int i=start;i<=end;i++){
            works[i] = newArrays[i-start];
        }
    }
}
